In this work we study the problem of actively learning binary classifiers from a given concept class, i.e., learning by utilizing unlabeled data and submitting targeted queries about their labels to a domain expert. We evaluate the quality of our solutions by considering the learning curves they induce, i.e., the rate of

Partial concepts are functions that can be undefined in certain parts of the input space.

" can be demonstrated by a finite set

A Polish space is a separable topological space that can be metrized by a complete metric. We move on to the discussion of universally measurable functions. Polish spaces are the same as Borel sets, from a probabilistic perspective. W e say that H has an infinite VCL tree if it has a VCL tree of depth d = 1 . We briefly discuss some important facts about Gale-Stewart games.

See Definitions 1.1 and 1.2 for the See [ 2, Section 2 and Appendix C] for more details. Before proceeding to the proof, we present the following result on learning partial concept classes. Recall the definition of VC is in the context of partial concepts (see Appendix A). 15 Theorem C.1 ([ 2 ], Theorem 34) The sample complexity of this model is defined formally in Definition E.1 . By taking the expectation on Eq. ( 3) we have, E We now prove Theorem 4.4 . Lemma C.2 (Agnostic sample compression generalization bound) We show that in our use case, we can deduce a stronger bound.

This work continues to investigate the link between differentially private (DP) and online learning. Alon, Livni, Malliaris, and Moran (2019) showed that for binary concept classes, DP learnability of a given class implies that it has a finite Littlestone dimension (equivalently, that it is online learnable). Their proof relies on a model-theoretic result by Hodges (1997), which demonstrates that any binary concept class with a large Littlestone dimension contains a large subclass of thresholds. In a follow-up work, Jung, Kim, and Tewari (2020) extended this proof to multiclass PAC learning with a bounded number of labels. Unfortunately, Hodges's result does not apply in other natural settings such as multiclass PAC learning with an unbounded label space, and PAC learning of partial concept classes. This naturally raises the question of whether DP learnability continues to imply online learnability in more general scenarios: indeed, Alon, Hanneke, Holzman, and Moran (2021) explicitly leave it as an open question in the context of partial concept classes, and the same question is open in the general multiclass setting. In this work, we give a positive answer to these questions showing that for general classification tasks, DP learnability implies online learnability. Our proof reasons directly about Littlestone trees, without relying on thresholds. We achieve this by establishing several Ramsey-type theorems for trees, which might be of independent interest.